/**
 * 三向切分的快速排序
 */
public class Quick3waySort extends QuickSort {
    @Override
    public void sort(Comparable[] a, int lo, int hi) {
        if (hi <= lo) {
            return;
        }
        int lt = lo, i = lo + 1, gt = hi;
        Comparable v = a[lo];

        while (i <= gt) {
            int cmp = a[i].compareTo(v);
            if (cmp < 0) {
                exch(a, lt++, i++);
            } else if (cmp > 0) {
                exch(a, i, gt--);
            } else {
                i++;
            } // 现在 a[lo..lt-1] < v = a[lt..gt] < a[gt+1..hi]成立
        }
        sort(a, lo, lt - 1);
        sort(a, gt + 1, hi);
    }

    public static void main(String[] args) {
        TemplateSort templateSort = new Quick3waySort();

        Comparable[] data = templateSort.createInt(0, 1000, 300);

        templateSort.run(data);
    }
}
